package binarySearch;

public class Main {

	public static void main(String[] args) {
		System.out.println("整数二分：");
		System.out.println(bsint(0,s.length-1));
		System.out.println("实数二分：");
		bsdouble(0,20);

	}

	//整数二分模板代码
	//被查数组,必须是递增或递减
	//问题：在数组中找小于28的最大值
	static int[] s = {5,8,15,17,25,28,30,34,39,45,52,60};
	//l:左界
	//r:右界
	static int bsint(int l,int r) {
		
		while(l<=r) {
			int mid = (l+r)/2;
			//check部分根据题目要求模拟
			if(check(mid)) {
				//找到了一个可行解
				//所有可行解中找个最大的
				System.out.println(mid);
				//找到一个可行情况，缩小左边界继续找
				l = mid + 1;     //要根据题意确定此处缩小左界还是右界
			}else {
				//没找到，缩小右边界
				r = mid - 1;     //要根据题意确定此处缩小左界还是右界
			}
		}
		//l是第一个大于28的数的位置
		//l指向的位置与check条件相关
		return l;
	}
	//检查是否小于28
	static boolean check(int mid) {
		return s[mid]<=28;
	}
	
	
	//实数二分模板代码
	//问题：计算20的三次方跟
	//l:左界
	//r:右界
	static double eps = 1e-6;  //设置有效精度1的负6次方
	static double bsdouble(double l,double r) {
		
		while(r-l>eps) {  //此处还可以用固定次数的循环，如for循环100次
			double mid = (l+r)/2;
			//check部分根据题目要求模拟
			if(check(mid)) {
				//找到了一个可行解
				//所有可行解中找个最大的
				System.out.println(mid);
				//找到一个可行情况，缩小左边界继续找，注意和整数二分有区别
				l = mid;     //要根据题意确定此处缩小左界还是右界
			}else {
				//没找到，缩小右边界，注意和整数二分有区别
				r = mid;     //要根据题意确定此处缩小左界还是右界
			}
		}
		return -1;
	}
	//检查mid的三次方是否小于20
	static boolean check(double mid) {
		return mid*mid*mid<=20;
	}
}
